#include <bits/stdc++.h>

using namespace std;

const int	Lim=100000;
const int	Lim_delta=100000;
const int	P1=25,P2=25,P3=25,P4=25;

int	n,m;
random_device	seed;
mt19937		RND(seed());

struct LCT
{
	struct node
	{
		int	val;
		bool	revf;
		node	*s[2],*fa;
		node() {}
		node(const int x){val=x,s[0]=s[1]=fa=0;revf=0;}

		bool	getlr() { return fa->s[1]==this; }
		bool	isroot() { return !fa || (fa->s[0]!=this && fa->s[1]!=this); }
		node *	link(const int w,node * t)
		{ if((s[w]=t))s[w]->fa=this; return this; }

		node *	access()
		{
			for(node * p=this,*q=0;p;q=p,p=p->fa)
			{
				p->splay();
				p->link(1,q);
				//p->update();
			} splay(); return this;
		}

		void	pdfr() { if(!isroot())fa->pdfr(); push_down(); }

		node *	splay()
		{
			pdfr();
			while(!isroot() && !fa->isroot())
			(getlr()==fa->getlr()?fa->rot():rot()),rot();
			if(!isroot())rot();
			//update();
			return this;
		}

		node * rot()
		{
			node * gfa=fa->fa;bool fl=fa->isroot();
			getlr()?link(0,fa->link(1,s[0])):link(1,fa->link(0,s[1]));
			//fa->update();
			if(!fl)gfa->link(gfa->s[1]==fa,this);
			else fa=gfa;
			return this;
		}

		void	reverse() { revf=!revf; pd(); }
		void	pd()
		{
			push_down();
			if(s[0])s[0]->push_down();
			if(s[1])s[1]->push_down();
		}

		void	push_down()
		{
			if(revf)
			{
				swap(s[0],s[1]);
				if(s[0])s[0]->revf=!s[0]->revf;
				if(s[1])s[1]->revf=!s[1]->revf;
				revf=0;
			} return ;
		}

		node *	get_top()
		{ node * t=this; while(!t->isroot())t=t->fa; return t; }

		node *	go_up()
		{ node * t=this; while(t->fa)t=t->fa; return t; }

		node *	get_root()
		{
			node * ss;
			for(ss=access();ss->pd(),ss->s[0];ss=ss->s[0]);
			return ss;
		}
	}U[110000];

	LCT() { }

	void	change_root(node * t)
	{
		t->access();
		t->reverse();
	}

	void	link(node * x,node *y)
	{
		if(x->get_root()==y->get_root())return ;
		change_root(y);y->fa=x; return ;
	}

	void	cut(node * x)
	{
		x->access();
		x->s[0]->fa=0;
		x->s[0]=0;
		//update();
		return ;
	}

	void	cut(node * x,node * y)
	{
		change_root(y);
		cut(x); return ;
	}

	pair<int,int>	Get_Linked_Edge()
	{
		while(true)
		{
			int x=RND()%n+1; if(!(U+x)->fa)continue;
			int temp=(U+x)->fa-U;
			cut((U+x)->fa,U+x); return make_pair(x,temp);
		}
		return make_pair(0,0);
	}

	pair<int,int>	Get_Unlinked_Edge()
	{
		int	x=RND()%n+1;
		node *	tt=(U+x)->go_up();
		while(true)
		{
			int	y=RND()%n+1;
			if(tt==(U+y)->go_up())continue;
			link(U+x,U+y); return make_pair(x,y);
		}
		return make_pair(0,0);
	}

	pair<int,int>	Get_Pair()
	{
		while(true)
		{
			int	x=RND()%n+1,y=RND()%n+1;
			//if((U+x)->get_root()!=(U+y)->get_root())continue;
			return make_pair(x,y);
		}
		return make_pair(0,0);
	}

	void	Get_Tree()
	{
		int	a[n+1];
		for(int i=1;i<=n;++i) a[i]=i,U[i]=node(i);
		shuffle(a+1,a+n+1,mt19937(seed()));
		for(int i=2;i<=n;++i)
			link(U+i,U+(RND()%(i-1)+1));
		return ;
	}

	void	Print_Tree()
	{
		for(int i=1;i<=n;++i)
			if((U+i)->fa)cout << (U+i)->fa-U << ' ' << i << endl;
		return ;
	}
	
	void	Pr(node * t)
	{
		if(t->s[0])printf("%5ld===L==>%5ld\n",t-U,t->s[0]-U),Pr(t->s[0]);
		if(t->s[1])printf("%5ld===R==>%5ld\n",t-U,t->s[1]-U),Pr(t->s[1]);
		return ;
	}

	void	Pr_tree()
	{
		printf("=====================================\n");
		for(int i=1;i<=n;++i)
		{
			if(U[i].isroot() && U[i].fa)
			{
				printf("%5ld---N-->%5d\n",U[i].fa-U,i),
				Pr(U[i].get_top());
			}
			if(U[i].isroot() && !U[i].fa)
				Pr(U[i].get_top());
		}
		return ;
	}
}S;

int main(int argc,char** argv)
{
	if(argc<3)return 0;

	int	T;
	n=atoi(argv[1]),m=atoi(argv[2]);

	cerr << "Creating Input File ..." << endl;
	if(argc==4)T=atoi(argv[3]);
	else	   T=1;
	cout << T << endl;
	while(T--)
	{
		cout << n << ' ' << m << endl;

		for(int i=1;i<=n;++i)
			cout << (int)RND()%(Lim+1) << ' ';
		cout << endl;

		S.Get_Tree();
		S.Print_Tree();
		//S.Pr_tree();

		for(int Kase=1;Kase<=m;++Kase)
		{
			int	op=RND()%100;
			//op=0;
			if(Kase==m)op=100;
			if(op<P1)//Change and Edge
			{
				pair<int,int> temp1=S.Get_Linked_Edge(),
					temp2=S.Get_Unlinked_Edge();
				cout << 1 << ' ';
				cout << temp1.first << ' ' << temp1.second << ' ';
				cout << temp2.first << ' ' << temp2.second << endl;
				continue;
			}
			else if(op<P1+P2)//Change val on path
			{
				pair<int,int> temp=S.Get_Pair();
				cout << 2 << ' ';
				cout << temp.first << ' ' << temp.second << ' ' << RND()%Lim_delta << endl;
				continue;
			}
			else if(op<P1+P2+P3)//Add val on path
			{
				pair<int,int> temp=S.Get_Pair();
				cout << 3 << ' ';
				cout << temp.first << ' ' << temp.second << ' ' << RND()%Lim << endl;
				continue;
			}
			else//Query second_Max val
			{
				pair<int,int> temp=S.Get_Pair();
				cout << 4 << ' ';
				cout << temp.first << ' ' << temp.second << endl;
				continue;
			}
		}
	}

	cerr << "Done." << endl;
	cerr << "Time Cost: " << (double)clock()/CLOCKS_PER_SEC << 's' << endl;

	return 0;
}
